package gold.digger;


import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC472 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * hard就是hard，思路要清晰明了
     * @return:
     */
    class Solution {

        class Trie {
            Trie[] m_chilren;
            boolean m_is_end;

            public Trie() {
                m_chilren = new Trie[26];
                m_is_end = false;
            }
        }

        Trie trie = new Trie();

        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> ans = new ArrayList<String>();

            Arrays.sort(words, (x, y) -> x.length() - y.length());

            for (int i = 0; i < words.length; i++) {
                if (words[i].length() == 0)
                    continue;

                if (dfs(words[i], 0))
                    ans.add(words[i]);
                else
                    insert_word(words[i], 0);
            }

            return ans;
        }

        public boolean dfs(String s, int pos) {
            if (s.length() == pos)
                return true;

            Trie tmp_trie = trie;

            for (int i = pos; i < s.length(); i++) {
                int c = s.charAt(i) - 'a';

                if (tmp_trie.m_chilren[c] == null)
                    return false;

                if (tmp_trie.m_chilren[c].m_is_end) {
                    if (dfs(s, i + 1))
                        return true;
                }

                tmp_trie = tmp_trie.m_chilren[c];
            }

            return false;
        }

        public void insert_word(String s, int node) {
            Trie tmp_trie = trie;

            for (int i = 0; i < s.length(); i++) {
                int c = s.charAt(i) - 'a';

                if (tmp_trie.m_chilren[c] == null)
                    tmp_trie.m_chilren[c] = new Trie();

                tmp_trie = tmp_trie.m_chilren[c];

                if (i == s.length() - 1)
                    tmp_trie.m_is_end = true;
            }
        }
    }


    class Solution_Complex_Thought {

        public class Node {
            boolean isWord;
            Node[] children;

            public Node(boolean isWord) {
                this.isWord = isWord;
                children = new Node[26];
            }
        }

        public class Trie {

            private Node root;

            public Trie() {
                this.root = new Node(false);
            }

            public void insert(String word) {
                Node node = root;
                for (char c : word.toCharArray()) {
                    int idx = c - 'a';
                    if (node.children[idx] == null) {
                        node.children[idx] = new Node(false);
                    }
                    node = node.children[idx];
                }
                node.isWord = true;
            }

            public boolean search(String word) {
                return search(word, 0, 0, root);
            }

            private boolean search(String word, int i, int misMatchCount, Node root) {
                if (misMatchCount > 1) {
                    return false;// mismatch two much.
                }

                if (i == word.length()) {
                    return misMatchCount == 1 && root.isWord;//mismatch just once and is final.
                }

                char c = word.charAt(i);
                int idx = c - 'a';
                for (int j = 0; j < 26; j++) {
                    if (root.children[j] == null) {
                        continue;
                    }
                    if (idx == j) {
                        if (search(word, i + 1, misMatchCount, root.children[j])) {
                            return true;
                        }
                    } else if (search(word, i + 1, misMatchCount + 1, root.children[j])) {
                        return true;
                    }
                }

                //如果当前字符没有后继者，并且word还没遍历完，则意味着不可能完成匹配
                return false;
            }
        }

        Trie trie = new Trie();

        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            for (String word : words) {
                trie.insert(word);
            }

            List<String> res = new ArrayList<>();
            dfsTrie(trie.root, new StringBuilder(), 0, res, 0);
            return res;
        }

        public void dfsTrie(Node root, StringBuilder curPath, int curPathLastStartPos, List<String> res, int level) {
            if (null == root) return;
            for (int i = 0; i < 26; i++) {
                if (null != root.children[i]) {
                    curPath.append((char) ('a' + i));
                    boolean addLevel = false;

                    if (root.children[i].isWord) {
                        if (level >= 1 && curPathLastStartPos > 0) {
                            // 当前已经是一个单词结尾 && 并且深度满足 && 当前part也在词组中
                            boolean curPartFound = trie.search(curPath.substring(curPathLastStartPos, curPath.length()));
                            if (curPartFound) {
                                res.add(curPath.toString());
                                curPathLastStartPos = curPath.length();
                                addLevel = true;
                            } else {
                                // 当前part虽然没有找到，但仍然需要dfs一次防止遗漏
                                dfsTrie(root.children[i], curPath, curPath.length(), res, level);
                            }
                        } else if (level == 0) {
                            curPathLastStartPos = curPath.length();
                            addLevel = true;
                        }
                    }

                    dfsTrie(root.children[i], curPath, curPathLastStartPos, res, level + (addLevel ? 1 : 0));
                    curPath.delete(curPath.length() - 1, curPath.length());
                }
            }
        }
    }

    public void run() {
        Solution solution = new Solution();
        String[] words = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
        System.out.println(solution.findAllConcatenatedWordsInADict(words));
    }

    public static void main(String[] args) throws Exception {
        LC472 an = new LC472();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
